#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int mySqrt(int x) {
        if (x < 2)
            return x;
        // int num = 0;
        // vector<int> v;
        // while(num<=x/2)
        // {
        //     v.push_back(num++);
        // }
        int left = 2, right = x;
        while (left < right)
        {
            long long mid = left + (right - left) / 2;
            long long vv = mid * mid;
            if (vv < x)
            {
                left = mid + 1;
            }
            else if (vv > x)
            {
                right = mid;
            }
            else
                return mid;
        }
        return left - 1;

    }
};